package com.example.demo.basics.hashmap;

/**
 * @author aqua
 * @description
 * 逻辑 构建链表数组对象Entry  k v next  get set(插入相同获取需要用到并覆盖)
 * 构建方法put get
 * 算出hash算法 hashcode^(h>>>16) 散列均匀
 * put逻辑 先找到index下标 判断有没有 有循环则判断k是否重复 有覆盖      否插入
 * get 先找到index下标 判断有没有 有重复循环找到相等的k value
 *
 *
 *  *  后续待更新扩容
 *  *  后续待更新红黑树 用treemap实现
 * @date 2020年11月02 22:33
 * @email 1301584033@qq.com
 */
public class HashMap<K,V> implements Map<K,V> {



    private  Entry<K,V>[] table=null;
    private int cap=16;
    private  int size=0;
    public HashMap() {
        table=new Entry[cap];
    }



    @Override
    public int hash(K key) {
        int h=0;
        if(key==null)h=0;
        else{
            h=key.hashCode() ^ (h >>> 16);
        }
        return Math.abs(h % cap);
    }
    /**
     * @Description: put 存储
     * 通过key进行哈希赛列算法 找到index位置
     * 算出数组位置实例化数组对象
     * 判断如果对象不为空就进行插入
     * 为空就是第
     * @Param: [k, v]
     * @return: V
     * @Author: aqua
     * @Date: 2020/11/2
     */

    @Override
    public V put(K k, V v) {
        int index=hash(k);
        Entry<K,V> newE=new Entry<>(k, v, index, null);
        Entry<K,V> entry=table[index];
        System.out.println(entry);
        //如果没有hash冲突 没有存过跳过 存在就赋值
        if (entry!=null) {
            while (true){
                if (entry.getKey().equals(k)) {
                    table[index].setValue(v);
                    return null;
                }
            }
        }else{
            if(k=="5"){
                System.out.println(index);
            }
            //直接存
            table[index] = new Entry<>(k, v, index, newE);

            size++;
        }
        return null;
    }
    public  int getSize(){
        return  this.size;
    }


    @Override
    public V get(K k) {
        int index=hash(k);
        Entry<K,V> entry=table[index];
        if(entry!=null){
            return findValue(k,entry);
        }
       return null;

    }

    public V findValue(K k,Entry<K,V> entry){
            if(entry.getKey().equals(k)||entry.getKey()==k){
                return entry.getValue();
            }else{
                if(entry.next!=null){
                    return findValue(k,entry);
                }
            }
        return  null;
    }

    /** 
    * @Description: 定义链表结构
    * @Param:  
    * @return:  
    * @Author: aqua
    * @Date: 2020/11/3 
    */ 
    private class  Entry<K,V> implements Map.Entry<K,V>{
        private  K k;
        private  V v;
        private  int hash;
        private  Entry<K,V> next;

        public Entry(K k, V v, int hash, Entry<K, V> next) {
            this.k = k;
            this.v = v;
            this.hash = hash;
            this.next = next;
        }

        @Override
        public K getKey() {
            return k;
        }

        @Override
        public V getValue() {
            return v;
        }

        @Override
        public void setValue(V v) {
            this.v=v;
        }
    }
    //测试
    public static void main(String[] args) {
        HashMap<String,String> hashMap=new HashMap<>();
        hashMap.put("1","1");
        hashMap.put("2","2");
        hashMap.put("3","3");
        hashMap.put("4","4");
        hashMap.put("5","5");

        System.out.println(hashMap.get("1"));
        System.out.println(hashMap.size);

    }
}
